{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3 Sum\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/0KPgom-f4syRJbG3EZslvQ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Given an array `nums` of $n$ integers, find all unique triplets (three numbers, $a$, $b$, & $c$) in `nums` such that $a+b+c=0$. Note that there may not be any triplets that sum to zero in `nums`, and that the triplets must not be duplicates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "```text\n",
    "Input: nums = [0, -1, 2, -3, 1]\n",
    "Output: [0, -1, 1], [2, -3, 1]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' Class Definition '''\n",
    "class Solution(object):\n",
    "    def threeSum(self, nums: list):\n",
    "        # Define a result list.\n",
    "        result = []\n",
    "        \n",
    "        # Sort the list ascending.\n",
    "        nums.sort()\n",
    "        \n",
    "        # Define 2 index pointer.\n",
    "        minimum = 0\n",
    "        maximum = len(nums) - 1\n",
    "        \n",
    "        # Keep checking until 2 index meet each other.\n",
    "        while minimum < maximum:\n",
    "            # Check if the triplets exists.\n",
    "            is_exist = (-(nums[minimum] + nums[maximum]) in nums)\n",
    "\n",
    "            if is_exist:\n",
    "                index = nums.index(-(nums[minimum] + nums[maximum]))\n",
    "                if index != minimum and index != maximum:\n",
    "                    result.append([\n",
    "                        nums[minimum],\n",
    "                        -(nums[minimum] + nums[maximum]),\n",
    "                        nums[maximum]\n",
    "                    ])\n",
    "            if nums[minimum] + nums[maximum] > 0:\n",
    "                maximum -= 1\n",
    "            elif nums[minimum] + nums[maximum] < 0:\n",
    "                minimum += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-2, 1, 1]]\n"
     ]
    }
   ],
   "source": [
    "''' Test Program '''\n",
    "nums = [1, -2, 1, 0, 5]\n",
    "print(Solution().threeSum(nums))\n",
    "# [[-2, 1, 1]]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
